﻿#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <utility>
#include <algorithm>
#include <unordered_map>
using namespace std;

//using ll = long long;
//
//void GetAns(vector<ll>& ans, int n, long long a0)
//{
//    ans[0] = ans[1] = a0;
//
//    ll a = a0, b = a0;
//    for (int i = 2; i < n; ++i)
//    {
//        ans[i] = a + b;
//        a = b;
//        b = ans[i];
//    }
//}
////
////int main()
////{
////    int n = 0;
////    vector<ll> ans;
////    vector<ll> in;
////
////    cin >> n;
////    in.resize(n);
////    ans.resize(n);
////
////    for (int i = 0; i < n; ++i)
////    {
////        cin >> in[i];
////    }
////
////    GetAns(ans, n - 2, in[0]);
////
////    int cnt = 0;
////    for (int i = 0; i < n; ++i)
////    {
////        if (in[i] != ans[i])
////            ++cnt;
////    }
////    cout << cnt << endl;
////
////    return 0;
////}
//
//
//
//// 123  3
//string Sum(string& a, string& b)
//{
//    string res;
//
//    reverse(a.begin(), a.end());
//    reverse(b.begin(), b.end());
//
//    int sz1 = a.size(), sz2 = b.size();
//    int flag = 0;
//    for (int i = 0, j = 0; i < sz1 || j < sz2 || flag; ++i, ++j)
//    {
//        int suma = i < sz1 ? (a[i] - '0') : 0;
//        int sumb = j < sz2 ? (b[i] - '0') : 0;
//        int sum = suma + sumb + flag;
//
//        if (sum / 10)
//            flag = 1;
//        else
//            flag = 0;
//        res.push_back(sum%10+'0');
//    }
//    reverse(a.begin(), a.end());
//    reverse(b.begin(), b.end());
//    reverse(res.begin(), res.end());
//
//    return res;
//}
//
//void GetAns(vector<string>& ans, int n, const string& a0)
//{
//    ans[0] = ans[1] = a0;
//
//    string a = a0, b = a0;
//    for (int i = 2; i < n; ++i)
//    {
//        ans[i] = Sum(a, b);
//        a = b;
//        b = ans[i];
//    }
//}
//
//int main()
//{
//    /*int n = 0;
//    vector<string> ans;
//    vector<string> in;
//
//    cin >> n;
//    ans.resize(n);
//    in.resize(n);
//
//    for (int i = 0; i < n; ++i)
//    {
//        cin >> in[i];
//    }
//
//    GetAns(ans, n - 2, in[0]);
//
//    int cnt = 0;
//    for (int i = 0; i < n; ++i)
//    {
//        if (in[i] != ans[i])
//            ++cnt;
//    }
//    cout << cnt << endl;*/
//
//    string s1 = "1";
//    string s2 = "1";
//
//    for (int i = 0; i < 31; ++i)
//    {
//        string sum = Sum(s1, s2);
//        cout << "【" << i + 3 << "】" << " ";
//        cout << s1 << " " << s2 << " " << sum << endl;
//
//        s1 = s2;
//        s2 = sum;
//    }
//
//    return 0;
//}


// Definition for a Node.
class Node 
{
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) 
    {
        val = _val;
        next = NULL;
        random = NULL;
    }
};

class Solution
{
public:
    vector<vector<string>> groupAnagrams1(vector<string>& strs)
    {
        int sz1 = strs.size();
        
        if (0 == sz1 || (1 == sz1 && 0 == strs[0].size()))
            return { {} };

        int index = 0;
        vector<vector<string>> vs;
        vector<bool> flag(strs.size(), false);
        vector<int> cnt1(26);
        vector<int> cnt2(26);

        for (int i = 0; i < sz1; ++i)
        {
            if (!flag[i])
            {
                vs.resize(index+1);

                Init(cnt1);
                for (int j = 0; j < strs[i].size(); ++j)
                {
                    ++cnt1[strs[i][j] - 'a'];
                }
                flag[i] = true;
                vs[index].push_back(strs[i]);

                for (int j = i + 1; j < sz1; ++j)
                {
                    Init(cnt2);
                    if (!flag[j])
                    {
                        for (int k = 0; k < strs[j].size(); ++k)
                        {
                            ++cnt2[strs[j][k] - 'a'];
                        }
                        
                        if (cnt1 == cnt2)
                        {
                            vs[index].push_back(strs[j]);
                            flag[j] = true;
                        }
                    }
                }

                ++index;
            }
        }

        return vs;
    }

    vector<vector<string>> groupAnagrams2(vector<string>& strs)
    {
        if (strs.empty() || (1 == strs.size() && strs[0] == ""))
            return { {""} };

        unordered_map<string, vector<string>> Map; // 遍历每个字符串 
        for (auto& s : strs)
        {
            string tmp = s; // 复制一份字符串 
            sort(tmp.begin(), tmp.end()); // 对字符串进行排序 
            Map[tmp].push_back(s); //
        }

        vector<vector<string>> ans;
        for (const auto& s : Map)
        {
            ans.push_back(s.second); // 将哈希表中的值组合起来 
        }

        return ans;
    }

    Node* copyRandomList(Node* head)
    {
        if (!head)
            return nullptr;

        Node* cur = head;
        map<Node*, Node*> Map;

        while (cur)
        {
            Node* newNode = new Node(cur->val);
            Map.insert({ cur, newNode });
            cur = cur->next;
        }

        for (const auto& e : Map)
        {
            e.second->next = Map[e.first->next];
            e.second->random = Map[e.first->random];
        }

        return Map[head];
    }

private:
    void Init(vector<int>& v)
    {
        for (int i = 0; i < 26; ++i)
        {
            v[i] = 0;
        }
    }
};

void Test1()
{
    int N = 0;
    int M = 0;
    string ns, ms;
    int cnt[26] = { 0 };

    cin >> N >> M >> ns;
    for (int i = 0; i < M; ++i)
    {
        char ch = 0;
        cin >> ch;
        ++cnt[ch - 'a'];
    }

    for (int i = 0; i < 26; ++i)
    {
        while (cnt[i]--)
        {
            ms += (i + 'a');
        }
    }

    string ans;
    int i = 0, j = 0;

    while (i < N && j < M)
    {
        if (ns[i] <= ms[j])
        {
            ans += ns[i++];
        }
        else
        {
            ans += ms[j++];
        }
    }

    while (i < N)
    {
        ans += ns[i++];
    }
    while (j < M)
    {
        ans += ms[j++];
    }

    cout << ans;
}

void Test2()
{
    vector<string> strs = {"eat","tea","tan","ate","nat","bat"};

    vector<vector<string>> vs = Solution().groupAnagrams2(strs);

    for (int i = 0; i < vs.size(); ++i)
    {
        for (int j = 0; j < vs[i].size(); ++j)
        {
            cout << vs[i][j] << " ";
        }
        cout << endl;
    }
}

void Test3()
{
    map<string, string> dict = { {"string", "字符串"}, {"left", "左边"}, {"sort", "排序"}};

    map<string, string>::iterator it = dict.begin();
    while (it != dict.end())
    {
        //cout << (*it).first << ":" << (*it).second << endl;
        
        // 显示调用，迭代器内部重载了operator->，返回pair对象的指针
        //cout << it.operator->()->first << ":" << it.operator->()->second << endl;
        // 特殊处理
        cout << it->first << ":" << it->second << endl;
        ++it;
    }
    cout << endl;

    // 有名对象
    pair<string, string> kv("test1", "测试1");
    dict.insert(kv);
    // 匿名对象
    dict.insert(pair<string, string>("test2", "测试2"));
    // 使用make_pair函数模板，返回一个pair对象
    dict.insert(make_pair("test3", "测试3"));
    // 隐式类型转换
    dict.insert({ "test4", "测试4" });
    dict.insert({ "test4", "测试4" });

    for (const auto& x : dict)
    {
        cout << x.first << ":" << x.second << endl;
    }
    cout << endl;

    string s;
    while (cin >> s)
    {
        it = dict.find(s);

        if (it != dict.end())
        {
            cout << it->first << ":" << it->second << endl;
        }
        else
        {
            cout << "不存在" << endl;
        }
    }
}

void Test4()
{
    string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" };
    map<string, int> cntMap;

    /*for (const auto& e : arr)
    {
        auto pos = cntMap.find(e);

        if (pos != cntMap.end())
        {
            ++cntMap[e];
        }
        else
        {
            cntMap.insert({e, 1});
            cout << "保存成功" << endl;
        }
    }*/

    for (const auto& e : arr)
    {
        // 已存在key，则修改value
        // 不存在key，则插入key后修改value
        ++cntMap[e];
    }

    for (const auto& x : cntMap)
    {
        cout << x.first << ":" << x.second << endl;
    }
    cout << endl;

}
int main()
{
    //Test1();
    //Test2();
    //Test3();
    Test4();


    return 0;
}